package _05_树.tree;

import org.w3c.dom.Node;

import java.util.Comparator;

/*
    AVL自平衡二叉搜索树
    平衡因子（Balance Factor）：某结点的左右子树的高度差
    AVL树的特点
    每个节点的平衡因子只可能是 1、0、-1（绝对值 ≤ 1，如果超过 1，称之为“失衡”）
    每个节点的左右子树高度差不超过 1  搜索、添加、删除的时间复杂度是 O(logn)
 */
public class AVLTree<E> extends BBST<E>{
    public AVLTree(){
        this(null);
    }

    //去调用父类的comparator然后初始化自己的比较器
    public AVLTree(Comparator<E> comparator){
        super(comparator);
    }

    //AVLTree自身的节点类
    private static class AVLNode<E> extends Node<E>{
        int height = 1; //特有的高度属性,新添加的都是叶子节点，默认设置高度为1
        public AVLNode(){
            this(null,null);
        }
        //调用父类的构造方法并初始化
        public AVLNode(E element,Node<E> parent){
            super(element,parent);
        }

        //计算平衡因子
        // 左子树的高度 - 右子树的高度
        public int balanceFactory(){
            int leftHeight = left == null ? 0 : ((AVLNode<E>)left).height;
            int rightHeight = right == null ? 0 : ((AVLNode<E>)right).height;
            return leftHeight - rightHeight; //返回左子树-右子树的高度差
        }

        //计算每个节点当前的高度
        public void updateHeight(){
            int leftHeight = left == null ? 0 : ((AVLNode<E>)left).height;
            int rightHeight = right == null ? 0 : ((AVLNode<E>)right).height;
            height = 1 + Math.max(leftHeight,rightHeight);
        }

        //找到左右子树最高的子树并返回
        public Node<E> tallerChild(){
            int leftHeight = left == null ? 0 : ((AVLNode<E>)left).height;
            int rightHeight = right == null ? 0 : ((AVLNode<E>)right).height;
            if(leftHeight>rightHeight) return left;
            if(rightHeight>leftHeight) return right;
            //如果一样高，看父节点是左还是右，就返回子的左还是右
            return isLeftChild() ? left : right;
        }

        @Override
        public String toString() {
            String parentString = "null";
            if(parent!=null){
                parentString =parent.element.toString();
            }
            return element+"_"+parentString+"_"+height;
        }

    }

    /**
     * 添加节点以后的自平衡的调整
     * 也可能在添加以后整颗AVL树都是平衡的
     * 需要找到最先失衡的祖先节点，对它进行自平衡调整，一旦它平衡以后，整颗树就都平衡
     * @param node 新添加的节点
     */
    @Override
    protected void afterAdd(Node<E> node) {
        //从父节点开始找，但是父节点不会失去平衡，一般是祖先节点失衡
        while((node = node.parent)!=null){
            if(isBalanced(node)){
                //如果是平衡的,更新高度即可
                updateHeight(node);
            }else{
                //不平衡，那就恢复平衡
                reBalance(node);
                break; //结束循环
            }
        }
    }

    /**
     * 删除节点以后的自平衡处理
     * 删除节点只会导致父节点以及祖先节点失去平衡，且最多只会导致一个节点失衡
     * 但是恢复平衡以后可能会导致更高的祖先节点失衡,所以需要O(logn)次平衡操作
     * @param node 待删除的节点|替代的子节点
     */
    @Override
    protected void afterRemove(Node<E> node) {
        //从父节点开始找，但是父节点不会失去平衡，一般是祖先节点失衡
        while((node = node.parent)!=null){
            if(isBalanced(node)){
                //如果是平衡的,更新高度即可
                updateHeight(node);
            }else{
                //不平衡，那就恢复平衡,但是可能导致更高的祖先节点失去平衡，所以继续循环修复平衡
                reBalance(node);
            }
        }
    }

    /**
     * 找到第一个,高度最低的不平衡的祖先节点，将其恢复平衡，一旦它平衡，整颗AVL就都平衡
     * 找到grand的左右子树高度最高的那一个节点parent，其次再找到parent的左右子树高度最高的那个子节点
     * @param grand 第一个不平衡的祖先节点
     */
    private void reBalance(Node<E> grand){
        Node<E> parent = ((AVLNode<E>)grand).tallerChild();
        Node<E> node = ((AVLNode<E>)parent).tallerChild();
        if(parent.isLeftChild()){ //左
            if(node.isLeftChild()){ //左 LL:对g进行右旋转
                rotateRight(grand);
            }else{ // LR:对p进行左旋转，对g进行右旋转
                rotateLeft(parent);
                rotateRight(grand);
            }
        }else{ //右
            if(node.isLeftChild()){ //RL:对p进行右旋转,对g进行左旋转
                rotateRight(parent);
                rotateLeft(grand);
            }else{ //RR:对g进行左旋转
                rotateLeft(grand);
            }
        }
    }

    //重写BBST中旋转后的统一操作，由于RBTree没有高度概念，所有需要重写此方法
    @Override
    protected void afterRotate(Node<E> grand, Node<E> parent, Node<E> child) {
        super.afterRotate(grand, parent, child);

        //更新节点的高度
        updateHeight(grand);
        updateHeight(parent);
    }

    //更新每个节点的高度
    private void updateHeight(Node<E> node){
        ((AVLNode<E>)node).updateHeight();
    }

    //判断是否平衡的方法
    private boolean isBalanced(Node<E> node){
        //拿到平衡因子的高度差
        //高度差<=1就是平衡
        return Math.abs(((AVLNode<E>) node).balanceFactory()) <= 1;
    }

    //AVL重写父类创建节点的方法
    @Override
    protected Node<E> createNode(E element, Node<E> parent) {
        return new AVLNode<>(element,parent);
    }
}
